package queueAndbfs;

import java.util.*;

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {

    public List<List<Integer>> levelOrder(Node root) {

        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) { return new ArrayList<>();}
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            List<Integer> tmp = new LinkedList<>();
            int size = queue.size();
            for(int i = 0; i < size; i++){
                Node cur = queue.poll();
                tmp.add(cur.val);
                for(Node c : cur.children){
                    if(c != null) { queue.add(c);}
                }
            }
            ret.add(tmp);
        }
        return ret;
    }


    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) { return new ArrayList<>();}
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 1;

        while(!queue.isEmpty()){
            List<Integer> tmp = new ArrayList<>();
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode cur = queue.poll();
                tmp.add(cur.val);
                if(cur.left != null) { queue.add(cur.left);}
                if(cur.right != null) { queue.add(cur.right);}
            }
            if(level % 2 == 0) { Collections.reverse(tmp);}
            ret.add(tmp);
            level++;
        }
        return ret;
    }


//    public int widthOfBinaryTree(TreeNode root) {
//        List<Pair<TreeNode, Integer>> queue = new ArrayList<>();
//        queue.add(new Pair<>(root, 1));
//        int ret = 0;
//
//        while(!queue.isEmpty()){
//            Pair<TreeNode, Integer> t1 = queue.get(0);
//            Pair<TreeNode, Integer> t2 = queue.get(queue.size() - 1);
//            ret = Math.max(ret, t2.getValue() - t1.getValue() + 1);
//
//            List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
//            for(Pair<TreeNode, Integer> t : queue){
//                TreeNode node = t.getKey();
//                int index = t.getValue();
//                if(node.left != null){
//                    tmp.add(new Pair<TreeNode, Integer>(node.left, index * 2));
//                }
//                if(node.right != null){
//                    tmp.add(new Pair<TreeNode, Integer>(node.right, index * 2 + 1));
//                }
//            }
//            queue = tmp;
//        }
//        return ret;
//    }

    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) { return ret;}
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        ret.add(root.val);

        while(!queue.isEmpty()){
            int size = queue.size();
            int x = Integer.MIN_VALUE;
            for(int i = 0; i < size; i++){
                TreeNode tmp = queue.poll();
                if(tmp.left != null){
                    queue.add(tmp.left);
                    x = Math.max(x, tmp.left.val);
                }
                if(tmp.right != null){
                    queue.add(tmp.right);
                    x = Math.max(x, tmp.right.val);
                }
            }
            if(queue.size() != 0) { ret.add(x);}
        }
        return ret;
    }

    public List<Integer> largestValues2(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) { return ret;}
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            int x = Integer.MIN_VALUE;
            for(int i = 0; i < size; i++){
                TreeNode tmp = queue.poll();
                x = Math.max(x, tmp.val);
                if(tmp.left != null){
                    queue.add(tmp.left);
                }
                if(tmp.right != null){
                    queue.add(tmp.right);
                }
            }
            ret.add(x);
        }
        return ret;
    }


}
